1 /* 2 * [The "BSD licence"] 3 * Copyright (c) 2005-2008 Terence Parr 4 * All rights reserved. 5 * 6 * Conversion to C#: 7 * Copyright (c) 2008 Sam Harwell, Pixel Mine, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. The name of the author may not be used to endorse or promote products 19 * derived from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 namespace Antlr.Runtime.Tree 34 { 35 public interface ITreeAdaptor<T> 36 { 37 #region Construction 38 39 /** <summary> 40 * Create a tree node from Token object; for CommonTree type trees, 41 * then the token just becomes the payload. This is the most 42 * common create call. 43 * </summary> 44 * 45 * <remarks> 46 * Override if you want another kind of node to be built. 47 * </remarks> 48 */ 49 T Create(IToken payload); 50 51 /** <summary>Duplicate a single tree node.</summary> 52 * <remarks>Override if you want another kind of node to be built.</remarks> 53 */ 54 T DupNode(T treeNode); 55 56 /** <summary>Duplicate tree recursively, using dupNode() for each node</summary> */ 57 T DupTree(T tree); 58 59 /** <summary> 60 * Return a nil node (an empty but non-null node) that can hold 61 * a list of element as the children. If you want a flat tree (a list) 62 * use "t=adaptor.nil(); t.addChild(x); t.addChild(y);" 63 * </summary> 64 */ 65 T Nil(); 66 67 /** <summary> 68 * Return a tree node representing an error. This node records the 69 * tokens consumed during error recovery. The start token indicates the 70 * input symbol at which the error was detected. The stop token indicates 71 * the last symbol consumed during recovery. 72 * </summary> 73 * 74 * </remarks> 75 * You must specify the input stream so that the erroneous text can 76 * be packaged up in the error node. The exception could be useful 77 * to some applications; default implementation stores ptr to it in 78 * the CommonErrorNode. 79 * 80 * This only makes sense during token parsing, not tree parsing. 81 * Tree parsing should happen only when parsing and tree construction 82 * succeed. 83 * </remarks> 84 */ 85 T ErrorNode(ITokenStream input, IToken start, IToken stop, RecognitionException e); 86 87 /** <summary>Is tree considered a nil node used to make lists of child nodes?</summary> */ 88 bool IsNil(T tree); 89 90 /** <summary> 91 * Add a child to the tree t. If child is a flat tree (a list), make all 92 * in list children of t. Warning: if t has no children, but child does 93 * and child isNil then you can decide it is ok to move children to t via 94 * t.children = child.children; i.e., without copying the array. Just 95 * make sure that this is consistent with have the user will build 96 * ASTs. Do nothing if t or child is null. 97 * </summary> 98 */ 99 void AddChild(T t, T child); 100 101 /** <summary> 102 * If oldRoot is a nil root, just copy or move the children to newRoot. 103 * If not a nil root, make oldRoot a child of newRoot. 104 * </summary> 105 * 106 * <remarks> 107 * old=^(nil a b c), new=r yields ^(r a b c) 108 * old=^(a b c), new=r yields ^(r ^(a b c)) 109 * 110 * If newRoot is a nil-rooted single child tree, use the single 111 * child as the new root node. 112 * 113 * old=^(nil a b c), new=^(nil r) yields ^(r a b c) 114 * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) 115 * 116 * If oldRoot was null, it's ok, just return newRoot (even if isNil). 117 * 118 * old=null, new=r yields r 119 * old=null, new=^(nil r) yields ^(nil r) 120 * 121 * Return newRoot. Throw an exception if newRoot is not a 122 * simple node or nil root with a single child node--it must be a root 123 * node. If newRoot is ^(nil x) return x as newRoot. 124 * 125 * Be advised that it's ok for newRoot to point at oldRoot's 126 * children; i.e., you don't have to copy the list. We are 127 * constructing these nodes so we should have this control for 128 * efficiency. 129 * </remarks> 130 */ 131 T BecomeRoot(T newRoot, T oldRoot); 132 133 /** <summary> 134 * Given the root of the subtree created for this rule, post process 135 * it to do any simplifications or whatever you want. A required 136 * behavior is to convert ^(nil singleSubtree) to singleSubtree 137 * as the setting of start/stop indexes relies on a single non-nil root 138 * for non-flat trees. 139 * </summary> 140 * 141 * <remarks> 142 * Flat trees such as for lists like "idlist : ID+ ;" are left alone 143 * unless there is only one ID. For a list, the start/stop indexes 144 * are set in the nil node. 145 * 146 * This method is executed after all rule tree construction and right 147 * before setTokenBoundaries(). 148 * </remarks> 149 */ 150 T RulePostProcessing(T root); 151 152 /** <summary>For identifying trees.</summary> 153 * 154 * <remarks> 155 * How to identify nodes so we can say "add node to a prior node"? 156 * Even becomeRoot is an issue. Use System.identityHashCode(node) 157 * usually. 158 * </remarks> 159 */ 160 int GetUniqueID(T node); 161 162 163 // R e w r i t e R u l e s 164 165 /** <summary> 166 * Create a node for newRoot make it the root of oldRoot. 167 * If oldRoot is a nil root, just copy or move the children to newRoot. 168 * If not a nil root, make oldRoot a child of newRoot. 169 * </summary> 170 * 171 * <returns> 172 * Return node created for newRoot. 173 * </returns> 174 * 175 * <remarks> 176 * Be advised: when debugging ASTs, the DebugTreeAdaptor manually 177 * calls create(Token child) and then plain becomeRoot(node, node) 178 * because it needs to trap calls to create, but it can't since it delegates 179 * to not inherits from the TreeAdaptor. 180 * </remarks> 181 */ 182 T BecomeRoot(IToken newRoot, T oldRoot); 183 184 /** <summary> 185 * Create a new node derived from a token, with a new token type. 186 * This is invoked from an imaginary node ref on right side of a 187 * rewrite rule as IMAG[$tokenLabel]. 188 * </summary> 189 * 190 * <remarks> 191 * This should invoke createToken(Token). 192 * </remarks> 193 */ 194 T Create(int tokenType, IToken fromToken); 195 196 /** <summary> 197 * Same as create(tokenType,fromToken) except set the text too. 198 * This is invoked from an imaginary node ref on right side of a 199 * rewrite rule as IMAG[$tokenLabel, "IMAG"]. 200 * </summary> 201 * 202 * <remarks> 203 * This should invoke createToken(Token). 204 * </remarks> 205 */ 206 T Create(int tokenType, IToken fromToken, string text); 207 208 /** <summary> 209 * Create a new node derived from a token, with a new token type. 210 * This is invoked from an imaginary node ref on right side of a 211 * rewrite rule as IMAG["IMAG"]. 212 * </summary> 213 * 214 * <remarks> 215 * This should invoke createToken(int,String). 216 * </remarks> 217 */ 218 T Create(int tokenType, string text); 219 220 #endregion 221 222 223 #region Content 224 225 /** <summary>For tree parsing, I need to know the token type of a node</summary> */ 226 int GetType(T t); 227 228 /** <summary>Node constructors can set the type of a node</summary> */ 229 void SetType(T t, int type); 230 231 string GetText(T t); 232 233 /** <summary>Node constructors can set the text of a node</summary> */ 234 void SetText(T t, string text); 235 236 /** <summary> 237 * Return the token object from which this node was created. 238 * Currently used only for printing an error message. 239 * The error display routine in BaseRecognizer needs to 240 * display where the input the error occurred. If your 241 * tree of limitation does not store information that can 242 * lead you to the token, you can create a token filled with 243 * the appropriate information and pass that back. See 244 * BaseRecognizer.getErrorMessage(). 245 * </summary> 246 */ 247 IToken GetToken(T t); 248 249 /** <summary> 250 * Where are the bounds in the input token stream for this node and 251 * all children? Each rule that creates AST nodes will call this 252 * method right before returning. Flat trees (i.e., lists) will 253 * still usually have a nil root node just to hold the children list. 254 * That node would contain the start/stop indexes then. 255 * </summary> 256 */ 257 void SetTokenBoundaries(T t, IToken startToken, IToken stopToken); 258 259 /** <summary>Get the token start index for this subtree; return -1 if no such index</summary> */ 260 int GetTokenStartIndex(T t); 261 262 /** <summary>Get the token stop index for this subtree; return -1 if no such index</summary> */ 263 int GetTokenStopIndex(T t); 264 265 #endregion 266 267 268 #region Navigation / Tree Parsing 269 270 /** <summary>Get a child 0..n-1 node</summary> */ 271 T GetChild(T t, int i); 272 273 /** <summary>Set ith child (0..n-1) to t; t must be non-null and non-nil node</summary> */ 274 void SetChild(T t, int i, T child); 275 276 /** <summary>Remove ith child and shift children down from right.</summary> */ 277 T DeleteChild(T t, int i); 278 279 /** <summary>How many children? If 0, then this is a leaf node</summary> */ 280 int GetChildCount(T t); 281 282 /** <summary> 283 * Who is the parent node of this node; if null, implies node is root. 284 * If your node type doesn't handle this, it's ok but the tree rewrites 285 * in tree parsers need this functionality. 286 * </summary> 287 */ 288 T GetParent(T t); 289 void SetParent(T t, T parent); 290 291 /** <summary> 292 * What index is this node in the child list? Range: 0..n-1 293 * If your node type doesn't handle this, it's ok but the tree rewrites 294 * in tree parsers need this functionality. 295 * </summary> 296 */ 297 int GetChildIndex(T t); 298 void SetChildIndex(T t, int index); 299 300 /** <summary> 301 * Replace from start to stop child index of parent with t, which might 302 * be a list. Number of children may be different after this call. 303 * </summary> 304 * 305 * <remarks> 306 * If parent is null, don't do anything; must be at root of overall tree. 307 * Can't replace whatever points to the parent externally. Do nothing. 308 * </remarks> 309 */ 310 void ReplaceChildren(T parent, int startChildIndex, int stopChildIndex, T t); 311 312 #endregion 313 } 314 } 315
